class Solution {
public:
    void generate(vector<string>& output, const string& seq, int n) {
        if (n == 0) {
            output.emplace_back(seq);
            return;
        }
        if (seq.empty() || seq[seq.size()-1] == '1') {
            generate(output, seq+'0', n-1);
            generate(output, seq+'1', n-1);
        } else {
            generate(output, seq+'1', n-1);
        }
    }
    vector<string> validStrings(int n) {
        vector<string> output;
        generate(output, "", n);
        return output;
    }
};